神 仙 题。
https://www.luogu.com.cn/problem/CF838D
题意
有排成一列的 $n$ 个座位，$m$ 名乘客依次上飞机。每个乘客都有一个目标座位，然后回选择从前门或者后门上飞机。上飞机后会先走到自己的目标座位，若目标座位已被占据，会向前走到第一个空位后坐下。如果没法找到合格的空位，那么就不能入座。
问有多少种目标座位和上前后门的安排方案使得所有人都能入座。
$n,m\le 10^6$。
题解
1 神仙转换：以前题目都是环不好考虑转换成序列。这道题目是序列不好考虑转换为环。我峨嵋你假设座位拍成一个环，$1$ 和 $n$ 之间夹了一个座位 $n+1$，我们不能走到 $n+1$ 上。
2 神仙转换：以前题目都是概率不好考虑转换为计数，这道题目是计数不好考虑转换为概率。我们计算每个人安排好且不到 $n+1$ 上的概率是多少。对于每一个位置，它被占据的概率位 $\frac{m}{n+1}$，所以答案位 $1-\frac{m}{n+1}$。
于是我们得到方案数为 $(2(n+1))^m\frac{n+1-m}{n+1}=2^m(n+1)^{m-1}(n+1-m)$。